// Esercizio 2.	
// Siano G e H due grafi orientati non pesati di n vertici 0,1,…, n-1 
// rappresentati con liste di adiacenza utilizzando la seguente struttura:
// 
// typedef struct graph {
//  		int   nv;
//  		edge   **adj; } graph;
//		
// graph *G, *H;
//
// typedef struct edge  {
// 	 int   key;
//	 struct   edge   *next; } edge;
//
//	
// scrivere in linguaggio C una funzione che restituisca un nuovo grafo T 
// intersezione dei due grafi G e H, 
// rappresentato con liste di adiacenza, 
// secondo la struttura dati graph definita sopra. 
// In pratica, T avrà tutti i vertici di G e H 
// e conterrà un arco da un nodo i a un nodo j 
// se e solo se tale arco è presente sia in G che in H. 
// Descrivere la complessità asintotica della funzione implementata.
//
// la funzione richiesta è graph *Intersezione(graph *G,graph *H)


#include <stdio.h>
#include <malloc.h>

typedef struct edge{
	int key;
	struct edge *next;
}edge;

typedef struct graph{
	int nv;
	edge **adj;
}graph;


graph *Intersezione(graph *G,graph *H)
{
graph *T;
int i, j, ok,*a;
edge *v, *new_ver;	
    
    ok=0;
    if ((G==NULL)||(H==NULL))
    {
       printf("I grafi non possono essere vuoti");
       ok=1;
    }   
    else
    {
       T=(graph *)malloc(sizeof(graph));
	   if (T==NULL) 
       {
          printf("memoria esaurita"); 
          ok=1;
       }
       else
       {
	      T->nv=G->nv;
	      T->adj=(edge **)malloc(sizeof(edge)*T->nv);
          if (T->adj==NULL) 
          {   
              printf("memoria esaurita");
              ok=1;
          }   
          else
          {
             a=(int *)malloc(sizeof(int)*T->nv);
             if (a==NULL)
             {  
                printf("memoria esaurita");
                ok=1;
             }
             else
             {
				for(i=0;i<T->nv;i++)
				{
                  a[i]=0;                                    
                  T->adj[i]=NULL;                   
                }    
				for(i=0;i<T->nv;i++)
				{
    				for(v=G->adj[i];v!=NULL;v=v->next)
                        a[v->key]++;
    				for(v=H->adj[i];v!=NULL;v=v->next)
                        a[v->key]++;
                    for(j=0;j<T->nv;j++)
				    {
                        printf(" \n verifica della doppia esistenza dell'arco %d --> %d",i,j);
                        if (a[j]==2) 
                        { 
                          new_ver=(edge*)malloc(sizeof(edge));
                          if (new_ver==NULL) 
                          {   
                              printf("memoria esaurita");
                              ok=1;
                              i=j=T->nv;
                          }   
                          else
                          {
                              new_ver->key=j;
                              new_ver->next=T->adj[i];             
                              T->adj[i]=new_ver;
                              printf(" \n nuovo arco aggiunto da %d a %d",i, T->adj[i]->key);
                          }
                        }
                        a[j]=0;
                    }
                }
             }
          }
       }
    }
    if (ok==1) T=NULL;
    return T;
}


graph *inizializza_grafo(int n)
{
 graph *G;
 int i;

 G=(graph *) malloc (sizeof(graph));
 if (G==NULL)//controlla se la memoria è stata allocata
	printf("\nERRORE! Non è possibile allocare memoria\n");
 else

 {
	G->adj=(edge**) malloc (n*sizeof(edge));
  if ((G->adj==NULL) && (n>0))//controlla se la memoria è stata allocata
  {
	printf("\nERRORE! Non è possibile allocare memoria\n");
	free(G);
	G=NULL;//annulla anche l'allocazione di sopra
  }

  else
  {
	 G->nv=n;
	for (i=0;i<n;i++)
		G->adj[i]=NULL;//tutti i vertici del grafo puntano a NULL
  }//end else
 }//end else
 return G;
}

void Insert_Arco(graph *G)
{int n,i,u,v;
edge *e,*tmp,*prec;
	printf("Quanti archi inserire?:");
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		printf("arco n° %d",i);
		printf("inserire nodo sorgente: ");
		scanf("%d",&u);
		printf("inserire nodo destinazione: ");
		scanf("%d",&v);
		tmp=(edge *)malloc(sizeof(edge));
		if(tmp==NULL)
			printf("memoria esaurita");
		else
		{
			tmp->key=v;tmp->next=NULL;
			if (G->adj[u]==NULL)
				G->adj[u]=tmp;
			else
			{	prec=G->adj[u];e=prec->next;
				while(e!=NULL)
				{prec=e;e=e->next;}
				prec->next=tmp;
			}
		}
	}
}

void stampa(graph *G)
{
 int i,ne=0;
 edge *e;

 if (G!=NULL)
 {
	printf("\nIl grafo ha %d vertici\n",G->nv);
	for (i=0;i<G->nv;i++)
	{
		e=G->adj[i];
		printf("\n%d",i);
		while (e!=NULL)
		{

			printf(" --> %d ",e->key);
			e=e->next;
			ne++;
		}
	}
	printf("\n\nIl grafo ha %d archi\n",ne);
 }
}


int main()
{
graph *G,*H,*Int;
int n;

do
{	
	printf("Inserire il num di nodi dei grafi:");
	scanf("%d",&n);
	G=inizializza_grafo(n);
	H=inizializza_grafo(n);
	printf("inserire gli archi per G:\n");
	Insert_Arco(G);
	printf("inserire gli archi per H:\n");
	Insert_Arco(H);
	Int=Intersezione(G,H);
	printf("\nINTERSEZIONE di G ed H:\n");
	stampa(Int);
    printf("\n premere 0 per uscire \n");
    scanf("%d",&n);
}
while(n!=0);	
}